import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：对链表进行插入排序
 * 思路：1. 把链表的转换为数组，对数组进行排序，将排序后的结果转换为链表
 * 优化：2. 创建一个哨兵节点，创建一个新链表，遍历原链表比较，进行插入排序
 */
public class Test {

    public static ListNode insertionSortList(ListNode head) {
        ListNode newHead = new ListNode(0, head);
        ListNode newCur = head;
        ListNode cur = head.next;
        while (cur != null) {
            // 链表中还有元素没有进行排序
            // 开始进行比较
            if (newCur.val <= cur.val) {
                // 说明已经有序了，只要把newCur往后移就行了
                newCur.next = new ListNode(cur.val);
                newCur = newCur.next;
            } else {
                // 找到小于的节点值，进行插入
                ListNode prev = newHead;
                // 不能找到最后来
                while (prev.next != newCur) {
                    // 说明找到了
                    if (prev.next.val >= cur.val) {
                        break;
                    }
                    prev = prev.next;
                }
                ListNode newNode = new ListNode(cur.val, prev.next);
                prev.next = newNode;
            }
            cur = cur.next;
        }
        newCur.next = null; // 要把最后的next置为null
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode head4 = new ListNode(3);
        ListNode head3 = new ListNode(1, head4);
        ListNode head2 = new ListNode(2, head3);
        ListNode head = new ListNode(4, head2);
        insertionSortList(head);
    }

    public void bubble_sort (ArrayList<Integer> array) {
        for (int i = 0; i < array.size()-1; i++) {
            boolean flag = true;
            for (int j = 1; j < array.size()-i; j++) {
                if (array.get(j-1) > array.get(j)) {
                    int tmp = array.get(j);
                    array.set(j, array.get(j-1));
                    array.set(j-1, tmp);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    public ListNode insertionSortList1(ListNode head) {
        // 转变为数组，排序之后再转为链表
        ArrayList<Integer> array = new ArrayList<>();
        while (head != null) {
            array.add(head.val);
            head = head.next;
        }
        // 对数组进行排序
        bubble_sort(array);
        ListNode newHead = new ListNode(array.get(0));
        ListNode cur = newHead;
        for (int i = 1; i < array.size(); i++) {
            cur.next = new ListNode(array.get(i));
            cur = cur.next;
        }
        return newHead;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}